Distributed computing architectures in which a variety of computing devices and/or applications communicate over a communication network may be used in electronic commerce environments, enterprise environments, and other computing environments. Given the variety and number of computing devices/applications in such architectures, a large volume of messages may be communicated between such devices and/or applications. Accordingly, a message queuing service may be used to act as an intermediary for messages sent between devices, applications or computing nodes within the computing architecture. The message queuing service may facilitate delivery of a message from a source device, application, or computing node (e.g., a message publisher) to one or more destination devices, applications, or computing nodes (e.g., a message consumer). A message queuing service may store and deliver such messages between publishers and consumers using destination queues.